\chapter{Kern-Algorithmus zur Berechnung von NOPs}\label{chapter:algo}
Dieses Kapitel beschreibt die Umwandlung der Methodik zur Berechnung von NOPs in einen Algorithmus mit einem bestimmten Format von Pseudocodes. Dabei wird die Komplexit"at des Algorithmus ausf"uhrlich analysiert, um die Implementierung der NOP-Engine zu erleichtern und die Korrektheit der Implementierung zu gew"ahrleisten.
\section{Weitere Konzepte f"ur den Algorithmus}
Vor der Umwandlung der Methodik in Pseudocodes werden noch einige weitere Konzepte vorgestellt, die zur Berechnung von NOPs erforderlich sind.
\subsubsection{Zeitdauerinformationen}
Bei {\bf Zeitdauerinformationen} handelt es sich um notierte Zeitdauerhandlungsweisen\footnote{Die Begriffe Zeitdauerhandlungsweisen und Aktionshandlungsweisen werden im Kapitel \ref{chapter:ground}, Abschnitt \ref{beh:group1} erl"autert.}. %(Siehe den Abschnitt \ref{beh:group1}). 
Eine Zeitdauerinformation enth"alt mehrere Zonen auf einer aufgetauchten Web-Seite in Bezug auf eine Web-Session eines Benutzers und ihre Zeitdauern. Ist eine Web-Seite zwei Mal innerhalb einer Web-Session aufgetreten, werden zwei Zeitdauerinformationen f"ur diese Web-Seite bez"uglich der Web-Session generiert. F"ur die Formeln \ref{formulaDurP} und \ref{formulaDurPExt} sollen Zeitdauerinformationen zur Verf"ugung stehen.
\subsubsection{Aktionsinformationen}
Bei Aktionsinformationen liegt die Betonung auf notierten Aktionshandlungsweisen. Eine Aktionsinformation besteht aus einer Aktion und ihrer Trigger-Position, n"amlich eine Zone, in Bezug auf eine Web-Session eines Benutzers. Die Formel \ref{formulaActP} verf"ugt "uber Aktionsinformationen als Eingaben. Besonders zu beachten, ist genauso wie bei Zeitdauerinformationen, dass zwei Auftritte einer Aktion bez"uglich einer Zone innerhalb einer Web-Session als zwei Aktionsinformationen betrachtet werden sollen.
\subsubsection{Benutzer-Session}
Bei einer {\bf Benutzer-Session} \engl{user session} handelt es sich um alle notierten Handlungsweisen, Zeitdauerinformationen und Aktionsinformationen, innerhalb einer Web-Session eines Benutzers. Sie soll beim Starten und Beenden der entsprechenden Web-Session angelegt bzw. gespeichert werden.
\subsubsection{NOP-Projekte}
{\bf NOP-Projekte} beinhalten die Einstellungsvariablen zur Berechnung von NOPs, n"amlich eine Strategie, und Aktualisierungsinformationen f"ur \kc{Benutzer-Sessionen} bzw. f"ur sich. Dies sind beispielsweise  die Anzahl der berechneten Benutzer-Sessionen und der letzte Aktualisierungszeitpunkt des NOP-Projekts usw. Sie sollten vor der Berechnung von NOPs erstellt werden und konfigurierbar sein. Zur Berechnung von NOPs wird ein NOP-Projekt als der einzige Input-Parameter des Algorithmus betrachtet.\\\\
Wir unterscheiden Benutzer-Sessionen durch NOP-Projekte. 
\begin{itemize}
\item {\bf Berechnete Benutzer-Sessionen}, die f"ur die Berechnung von NOP's in Bezug auf ein NOP-Projekt beigetragen haben.
\item {\bf Neue Benutzer-Sessionen}, die noch keine Beitr"age zur Berechnung von NOPs  in Bezug auf ein NOP-Projekt gegeben haben.
\end{itemize}

\section{"Ubersetzung der Methodik zur Berechnung von NOPs im Algorithmus}\label{section:algo}
%Ausgehend von den im Abschnitt \ref{section:methodik} erl"auterten Formeln 
In diesem Abschnitt wird die Methodik\footnote{Die Methodik zur Berechnung von NOPs wird im Kapitel \ref{chapter:ground}, Abschnitt \ref{section:methodik} erl"autert.} zur Berechnung von NOPs im Algorithmus als Pseudocodes "ubersetzt. Dieser umgewandelte Algorithmus wird in dieser Arbeit als Kern-Algorithmus der NOP-Engine bezeichnet. Ausgehend von den mathematischen Formeln der Methodik wird der Kern-Algorithmus wegen seiner Komplexit"at in eine Start-Funktion und drei Subroutinen zerlegt. Im Folgenden werden sie mit Hilfe von den obenerw"ahnten Konzepten ausf"uhrlich erl"autert.
\subsection{Einsch"atzung des m"oglichen Auftritts der Instanzen der Konzepte}\label{section:attention}
Vor dem Starten des Gugubarra-Projekts wurde eingesch"atzt, dass die m"oglichen Auftritte von Zonen, Aktionen und Themen maximal ein hundert sein sollten, und die Anzahl der Benutzern einer Web-Site mehr als eine Million sein kann. D.h. es besteht die M"oglichkeit, dass die Anzahl der Benutzer-Sessionen sehr gro"s ist\footnote{F"ur ein Portal kann es hundert Millionen Benutzer-Sessionen f"ur die registrierte Benutzer geben.}. Im umgewandelten Algorithmus sollte eine Auflistung der vorhandenen Benutzer bzw. ihrer Benutzer-Sessionen einer Web-Site vermieden werden, um die Performance des Algorithmus zu erh"ohen. 
\subsection{Berechnung der NOPs in Bezug auf ein NOP-Projekt}
Im folgenden Codeblock wird die Start-Funktion des Kern-Algorithmus mit dem Namen {\em calculateNops} in Pseudocodes dargestellt. Die Eingabe dieser Funktion ist ein NOP-Projekt. Zwischen die Zeile 8 und 12 steht eine Schleife, mit der die neuen Benutzer-Sessionen in Bezug auf das eingegebene NOP-Projekt einer nach dem anderen durch die vordefinierte Variable {\em us\_next(p)} ausgelesen, und das NOP eines Benutzers durch die Subroutine {\em calculateNop} bzw. die aktuelle Benutzer-Session ausgewertet wird. Dadurch wird eine Auflistung aller neuen Benutzer-Sessionen in Bezug auf das eingegebene NOP-Projekt vermieden, und die Performance des Algorithmus gew"ahrleistet.\\
\includepseudocode{chapters/algo/pc_calculat_nops.pc}
\subsection{Berechnung eines NOPs einer neuen Benutzer-Session in Bezug auf ein eingegebenes NOP-Projekt}
Zur Berechnung eines NOPs f"ur eine neue Benutzer-Session in Bezug auf ein eingegebenes NOP-Projekt wird eine neue Subroutine {\em calculateNop} erstellt. Im darunterliegenden Pseudocode wird diese Subroutine detailliert beschrieben. Zwischen den Zeilen 17 und 23 werden alle Einstellungsvariablen zur Berechnung eines NOPs geladen. Die Operation {\em CLONE} steht daf"ur zur Verf"ugung, dass das neue NOP des Benutzers "uber alle Themen und ihrer Gewichten des aktuellen NOPs verf"ugen kann. Dadurch konzentriert sich die Berechnung nur auf die vorhandene Themen des aktuellen NOPs bzw. die neuen Themen, die in der neuen Benutzer-Session aufgetreten sind. So wird eine Auflistung aller vordefinierten Themen einer Web-Site f"ur die folgende Schleife vermieden. In der zwischen den Zeilen 27 und 37 stehenden Schleife werden die Thema-Gewichte anhand der im Kapitel \ref{chapter:ground} definierten Formeln berechnet. Dabei werden zwei weitere Subroutinen, sowie {\em DurP} und {\em ActP}, zur Berechnung des Zeitdauerprofils bzw. Aktionsprofils\footnote{Die Begriffe Zeitdauerprofil und Aktionsprofil werden im Kapitel \ref{chapter:ground}, Abschnitt \ref{durP} und \ref{actP} erl"autert.} dargestellt.\\
\includepseudocode{chapters/algo/pc_calculat_nop.pc}
\subsection{Berechnung eines Zeitdauerprofils}
Die Subroutine {\em DurP} beschreibt die Formel \ref{formulaDurP} und \ref{formulaDurPExt} zur Berechnung eines Zeitdauerprofils. Diese Berechnung ist stark von der Seitenregel und dem prominenten Faktor\footnote{Die Begriffe Seitenregel und prominenter Faktor werden im Kapitel \ref{chapter:ground}, Abschnitt \ref{durP} erl"autert.} abh"angig. Der zwischen den Zeilen 21 und 38 stehende Pseudocode wertet das Gewicht eines Themas mit der eingegebenen Seitenregel aus. Dann folgt die Multiplikation dieses Thema-Gewichts mit dem prominenten Faktor, falls er aktiviert ist. Dadurch wird ein automatisches Selektieren aus der Formel \ref{formulaDurP} und \ref{formulaDurPExt} erm"oglicht.\\
\includepseudocode{chapters/algo/pc_calculate_durP.pc} 
\subsection{Berechnung eines Aktionsprofils}
Die Subroutine {\em ActP} wird f"ur die Formel \ref{formulaActP} zur Verf"ugung gestellt. Die erste Schleife berechnet die Summe aller Gewichte der Aktionen, die in den Aktionsinformationen der aktuellen Benutzer-Session aufgetaucht sind. Zwischen den Zeilen 16 und 18 wird "uberpr"upt, ob diese Summe gleich 0 ist. Wenn ja, wird diese Subroutine abgebrochen, und liefert 0 als Ergebnis zur"uck, um zu vermeiden, der Nenner der Formel \ref{formulaActP} gleich 0 ist. Die zweite Schleife berechnet das Aktionsprofil eines Themas. Dabei sollen die Gewichte bzw. die Trigger-Positionen der Aktionen aus den Aktionsprofilen der eingegebenen Benutzer-Session ausgelesen werden.
\includepseudocode{chapters/algo/pc_calculate_actP.pc} 
\section{Komplexit"at des Algorithmus}
%Die Komplexit"at des Kern-Algorithmus von dem NOP-Engine ist schwer zu berechnen
Hierbei wird nur der schlimmste Fall \engl{worst-case}  betrachtet. Ausgehend von der Start-Funktion {\em calculateNops} ist der Kern-Algorithmus der NOP-Engine nur von den neuen Benutzer-Sessionen in Bezug auf das eingegebene NOP-Projekt abh"angig. Die Anzahl der neuen Benutzer-Sessionen wird als $\sharp(us)$ bezeichnet. Bei der Kalkulation eines neuen NOPs mit der Subroutine {\em calculateNop} werden nur die Themen in der eingegebenen Benutzer-Session bzw. in dem alten NOP betroffen. Wir schreiben die Kosten der Funktion als $O(\sharp(topic))$. In der Schleife der Subroutine {\em DurP} ist der Zeitaufwand von der Anzahl der Zeitdauerinformationen und der betroffenen Zonen abh"angig. Die Kosten zur Berechnung eines Zeitdauerprofils ist $O(\sharp(si)*\sharp(zone))$. F"ur die Schleife der Subroutine {\em ActP} werden die meisten Beitr"age des Zeitaufwands von den Aktionsinformationen, die die eingegebene Benutzer-Session beinhalten, und den betroffenen Zonen gegeben. Sie wercen als $O(\sharp(si)*\sharp(zone))$ geschrieben. Die Kosten des Kern-Algorithmus der NOP-Engine sind die folgenden,
\[O(\sharp(us))*O(\sharp(topic))*\Big(O(\sharp(si)*\sharp(zone)) + O(\sharp(ai)*\sharp(zone))\Big)\] 
wobei
\begin{itemize}
\item $\sharp(us)$ die Anzahl der neuen Benutzer-Sessionen f"ur das NOP-Projekt $p$ ist,
\item $\sharp(si)$ die Anzahl der Zeitdauerinformationen  einer Benutzer-Session bezeichnet, und
\item $\sharp(ai)$ die Anzahl der Aktionsinformationen einer Benutzer-Session beschreibt.
\end{itemize}
Angesichts der Einsch"atzung im Abschnitt \ref{section:attention} ist die Anzahl von Themen einer Web-Site maximal 100 und die Anzahl von Zonen einer Web-Site darf auch nicht unendlich sein. Dies hei"st, dass $O(\sharp(topic))$ und $O(\sharp(zone))$ Konstanten sind. Somit wird der Aufwand des Kern-Algorithmus von dem NOP-Engine wie folgt dargestellt, 
\[O(\sharp(us))*\Big(O(\sharp(si) + O(\sharp(ai))\Big)
 = O\Big(\sharp(us)*(\sharp(si) + \sharp(ai))\Big)\] 
Der Kern-Algorithmus ist nur abh"angig von der Anzahl der neuen Benutzer-Sessionen bzw. ihrer Zeitdauerinformationen und Aktionsinformationen in Bezug auf das eingegebene NOP-Projekt. Die Effizienz ist dadurch gezeigt.
\section{Zusammenfassung}
In diesem Kapitel wird die Methodik zur Berechnung von NOPs in Pseudocodes umgewandelt und als der Kern-Algorithmus der NOP-Engine dargestellt. Der Aufwand des Kern-Algorithmus ist 
\[O\Big(\sharp(us)*(\sharp(si) + \sharp(ai))\Big)\]
und zeigt dabei die Effizienz des Kern-Algorithmus. Im Verlauf der weiteren Arbeit wird dargestellt, wie das System NOP-Engine Schritt f"ur Schritt implementiert wird.


